package leetcode_900;

/**
 *@author 周杨
 *PushDominoes_838 多米诺骨牌游戏 看最终的牌是倒向哪个方向
 *describe:用左右数组标记 AC 56%
 *2018年11月1日 下午2:34:45
 */
public class PushDominoes_838 {
	public static void main(String[] args) {
		PushDominoes_838 test=new PushDominoes_838();
		test.pushDominoes(".L.R...LR..L..");
	}
	
	public String pushDominoes(String dominoes) {
        char []chars=dominoes.toCharArray();
        int []right=new int[chars.length];
        int []left=new int[chars.length];
        if(chars[0]=='R')
        	right[0]=1;
        else
        	right[0]=-1;//没有决定权
        for(int i=1;i<chars.length;++i) {
        	if(chars[i]=='R')
        		right[i]=1;
        	else if(chars[i]=='L'){
        		right[i]=-1;
        	}
        	else {//没有决定权
        		if(right[i-1]==-1)
        			right[i]=-1;
        		else
        			right[i]=1+right[i-1];
        	}
        }
        left[chars.length-1]=chars[chars.length-1]=='L'?1:-1;
        for(int i=chars.length-2;i>=0;--i) {
        	if(chars[i]=='L')
        		left[i]=1;
        	else if(chars[i]=='R')
        		left[i]=-1;
        	else {
        		if(left[i+1]==-1)
        			left[i]=-1;
        		else
        			left[i]=1+left[i+1];
        	}
        }
        
        for(int i=0;i<chars.length;++i) {
        	if(left[i]==right[i])
        		continue;
        	if(left[i]==-1)
        		chars[i]='R';
        	else if(right[i]==-1)
        		chars[i]='L';
        	else if(left[i]<right[i]) {
        		chars[i]='L';
        	}
        	else
        		chars[i]='R';
        }
        return new String(chars);
    }
}
